# -*- coding: utf-8 -*-
# created by Alberthch - 陈航  2021/7/15 15:29
# Description:怎样实现一个按优先级排序的队列？并且在这个队列上每次pop操作总是返回优先级最高的那个元素


# 1)、以单下划线开头，表示这是一个保护成员，只有类对象和子类对象自己能访问到这些变量。以单下划线开头的变量和函数被默认当作是内部函数，
#   使用from module improt *时不会被获取，但是使用import module可以获取
#
# (2)、以单下划线结尾仅仅是为了区别该名称与关键词
#
# (3)、双下划线开头，表示为私有成员，只允许类本身访问，子类也不行。在文本上被替换为_class__method
#
# (4)、双下划线开头，双下划线结尾。一种约定，Python内部的名字，用来区别其他用户自定义的命名,以防冲突。
#   是一些 Python 的“魔术”对象，表示这是一个特殊成员，例如：定义类的时候，若是添加__init__方法，那么在创建类的实例的时候，
#   实例会自动调用这个方法，一般用来对实例的属性进行初使化，Python不建议将自己命名的方法写为这种形式。

import heapq


class PriorityQueue:
    # _queue保存元素
    # _index
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        # heappush(heap,item) #往堆中插入一条新的值
        # 默认建立小顶堆，-priority表示按优先级从高到低，但堆元素是个元组，以第一个元素值-priority进行堆的构建
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        # heapq.heappop() 函数弹出堆中最小值，按照-priority值
        # 弹出并返回堆顶元素
        return heapq.heappop(self._queue)[-1]


# Example use
class Item:
    def __init__(self, name):
        self.name = name

    # 因为python中的class都直接或间接地继承Object class，这个class都有__repr__这个function，
    # 当我们打印class时，其实打印的就是这个function的返回值，不同情况下打印的信息会是“类名+object at+内存地址”信息，
    # 但是我们可以通过重写这个方法来定义打印class的信息了。
    def __repr__(self):
        return 'Item({!r})'.format(self.name)


q = PriorityQueue()

q.push(Item('foo'), 1)
q.push(Item('bar'), 5)
q.push(Item('spam'), 4)
q.push(Item('grok'), 1)

print("逐个弹出堆顶元素：")
print("Should be bar:", q.pop())
print("Should be spam:", q.pop())
print("Should be foo:", q.pop())
print("Should be grok:", q.pop())
